#ifndef MSC_STREE_H
#define MSC_STREE_H

#include "mem_base.h"
#include "rbtree.h"
#include <string.h>

//sort tree
//特性：
//(1) 每个节点或者是黑色，或者是红色。
//(2) 根节点是黑色。
//(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
//(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
//(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

#ifndef MS_TREEKEY
//#define MS_TREEKEY int //test
#define MS_TREEKEY void*
#endif

#define MS_RBTREE_RED			1
#define MS_RBTREE_BLACK 			0

#pragma pack(push,1)
typedef struct ms_stree_node_s {
    struct ms_stree_node_s* parent;
    struct ms_stree_node_s* left;
    struct ms_stree_node_s* right;
    size_t color : 1;
    size_t key : msc_rbtree_key_sizebit;
    unsigned char p[0];
} ms_stree_node_t, *ms_stree_node;
#pragma pack(pop)

typedef struct {
    void (*construct)(void* self);
    void (*destroy)(void* self);
    void (*copy)(void* self, void* other);
    MS_TREEKEY (*key_fn)(void* v);
    bool (*key_cmp)(MS_TREEKEY left, MS_TREEKEY right);
}ms_stree_funs;

typedef struct ms_stree_s {
    ms_alloc_t* ac;
    ms_stree_node sentinel; //哨兵节点
    size_t size;    //元素大小：0表示是指针, 整数，item的data直接赋值
    ms_stree_funs fs;
} ms_stree_t, *ms_stree;


static inline MS_TREEKEY ms_stree_key(void* node) {
    return (MS_TREEKEY)(((ms_stree_node)node)->key);
}

static inline bool ms_stree_less(MS_TREEKEY left, MS_TREEKEY right) {
    return (size_t)left < (size_t)right;
}

CPUBLIC ms_stree ms_stree_create(ms_alloc_t* ac, size_t size, ms_stree_funs* fs) {
    if (!ac) {
        ac = ms_global_alloc();
    }
    ms_stree t = (ms_stree)ms_allocate(ac, sizeof(ms_stree_t));
    if (t) {
        t->ac = ac;
        t->sentinel = (ms_stree_node)ms_allocate(ac, sizeof(ms_stree_node_t));
        if (t->sentinel) {
			MS_RBTREE_INIT(t->sentinel);
            if (size)
                t->size = size;
            else
                t->size = msc_size_ptr_;
            if(fs)
                t->fs = *fs;
            else
                memset(&t->fs, 0, sizeof(ms_stree_funs));
            if (!t->fs.construct)
                t->fs.construct = ms_type_used;
            if (!t->fs.destroy)
                t->fs.destroy = ms_type_used;
            if (!t->fs.copy)
                t->fs.copy = ms_type_copy_default;
            if (!t->fs.key_fn)
                t->fs.key_fn = ms_stree_key;
            if (!t->fs.key_cmp)
                t->fs.key_cmp = ms_stree_less;
        }
        else {
            ms_deallocate(ac, t);
            t = NULL;
        }
    }
    return t;
}

static inline void ms_stree_delete_root(ms_stree t, ms_stree_node root) {
    if (NULL == root || root == t->sentinel) {
        return ;
    }
    ms_stree_delete_root(t, root->left);
    ms_stree_delete_root(t, root->right);
    t->fs.destroy(root->p);
    ms_deallocate(t->ac, root);
}

CPUBLIC void ms_stree_clear(ms_stree t) {
#ifdef _IF_NULL_
    if (t) {
#endif
        if (!MS_RBTREE_EMPTY(t->sentinel)) {
            ms_stree_delete_root(t, t->sentinel->parent);
			MS_RBTREE_INIT(t->sentinel);
        }
#ifdef _IF_NULL_
    }
#endif
}

CPUBLIC void ms_stree_destory(ms_stree t) {
#ifdef _IF_NULL_
    if (t) {
#endif
        ms_stree_delete_root(t, t->sentinel->parent);
        ms_deallocate(t->ac, t);
#ifdef _IF_NULL_
    }
#endif
}

CPUBLIC bool ms_stree_empty(ms_stree t) {
    return NULL == t || MS_RBTREE_EMPTY(t->sentinel);
}

CPUBLIC size_t ms_stree_size(ms_stree t) {
#ifdef _IF_NULL_
    if (t) {
#endif
    return MS_RBTREE_SIZE(t->sentinel);
#ifdef _IF_NULL_
    }
    return 0;
#endif
}

//插入节点，如果old_data为NULL表示允许重复
CPUBLIC ms_stree_node ms_stree_insert(ms_stree t, void* data, bool bMulti) {
#ifdef _IF_NULL_
    if (t) {
#endif
    if (MS_RBTREE_EMPTY(t->sentinel)) {
        ms_stree_node node = (ms_stree_node)ms_allocate(t->ac, sizeof(ms_stree_node_t)+t->size);
        if (node) {
            node->parent = node->left = node->right = t->sentinel;
            t->fs.construct(node->p);
            t->fs.copy(node->p, data);
            node->color = MS_RBTREE_BLACK;
            t->sentinel->parent = node;
            ++t->sentinel->key;
            return node;
        }
    }
    //查找插入位置
    MS_TREEKEY key = t->fs.key_fn(data);
    ms_stree_node p = (ms_stree_node)MS_RBTREE_TOP(t->sentinel);
    ms_stree_node trynode = p;
    bool _addleft = false;
    if (bMulti) {
        //允许重复
        while (trynode != t->sentinel) {
            p = trynode;
            if (t->fs.key_cmp(key, t->fs.key_fn(trynode->p))) { //如果有重复的放在最右边
                trynode = trynode->left;
                _addleft = true;
            }
            else {
                trynode = trynode->right;
                _addleft = false;
            }
        }
    }
    else {
        //不允许重复
        while (trynode != t->sentinel) {
            p = trynode;
            if (t->fs.key_cmp(key, t->fs.key_fn(trynode->p))) { //如果有重复的放在最右边
                trynode = trynode->left;
                _addleft = true;
            }
            else {
                if (!t->fs.key_cmp(t->fs.key_fn(trynode->p), key)) {
                    //重复
                    t->fs.copy(trynode->p, data);
                    return trynode;

                }
                trynode = trynode->right;
                _addleft = false;
            }
        }
    }
    ms_stree_node node = (ms_stree_node)ms_allocate(t->ac, sizeof(ms_stree_node_t)+t->size);
    if (node) {
        node->parent = p;
        t->fs.construct(node->p);
        t->fs.copy(node->p, data);
        node->color = MS_RBTREE_RED;
        if (_addleft) {
            p->left = node;
        }
        else {
            p->right = node;
        }
        node->left = node->right = t->sentinel;
        ++t->sentinel->key;
        //修正调整
        ms_rbtree_fixup_i((ms_rbtree_p)t->sentinel, (ms_rbtree_p)node);
        return node;
    }
    return t->sentinel;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

#define ms_stree_insert_s(t, d) ms_stree_insert(t, d, false)
#define ms_stree_insert_m(t, d) ms_stree_insert(t, d, true)

//查询节点
CPUBLIC ms_stree_node ms_stree_find(ms_stree t, MS_TREEKEY key) {
#ifdef _IF_NULL_
    if (t) {
#endif
    ms_stree_node node = (ms_stree_node)MS_RBTREE_TOP(t->sentinel);
    while (node != t->sentinel) {
        if (t->fs.key_cmp(key, t->fs.key_fn(node->p))) {
            node = node->left;
        }
        else if (t->fs.key_cmp(t->fs.key_fn(node->p), key)){
            node = node->right;
        }
        else {
            return node;
        }
    }
    return t->sentinel;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC void* ms_stree_node_data(ms_stree_node node) {
#ifdef _IF_NULL_
	if (node) {
#endif
	return node->p;
#ifdef _IF_NULL_
	}
	return NULL;
#endif
}
//删除一个节点，总共分三种情况
// 1.被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
// 2.被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
// 3.被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；
//之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。
//这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。
//既然"它的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有子节点，要么只有一个子节点。
//若没有子节点，则按"情况① "进行处理；若只有一个子节点，则按"情况② "进行处理。

CPUBLIC void ms_stree_remove(ms_stree t, ms_stree_node node) {
#ifdef _IF_NULL_
    if (t && node && node != t->sentinel) {
#endif
    MS_RBTREE_REMOVE(t->sentinel, node);
    //删除
    ms_deallocate(t->ac, node);
#ifdef _IF_NULL_
    }
#endif
}

CPUBLIC ms_stree_node ms_stree_begin(ms_stree t) {
#ifdef _IF_NULL_
    if (t) {
#endif
    return (ms_stree_node)MS_RBTREE_MINIMUM(t->sentinel, MS_RBTREE_TOP(t->sentinel));
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC ms_stree_node ms_stree_next(ms_stree t, ms_stree_node node) {
    return (ms_stree_node)MS_RBTREE_SUCCESSOR(t->sentinel, node);
}

CPUBLIC ms_stree_node ms_stree_end(ms_stree t) {
#ifdef _IF_NULL_
    if (t) {
#endif
    return t->sentinel;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC ms_stree_node ms_stree_rbegin(ms_stree t) {
#ifdef _IF_NULL_
    if (t) {
#endif
    return (ms_stree_node)MS_RBTREE_MAXIMUM(t->sentinel, MS_RBTREE_TOP(t->sentinel));
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC ms_stree_node ms_stree_rnext(ms_stree t, ms_stree_node node) {
#ifdef _IF_NULL_
    if (t) {
#endif
    return (ms_stree_node)MS_RBTREE_PREDECESSOR(t->sentinel, node);
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC ms_stree_node ms_stree_rend(ms_stree t) {
#ifdef _IF_NULL_
    if (t) {
#endif
    return t->sentinel;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}
//not less than key
CPUBLIC ms_stree_node ms_stree_lower_bound(ms_stree t, MS_TREEKEY key) {
#ifdef _IF_NULL_
    if (t) {
#endif
    ms_stree_node node = (ms_stree_node)MS_RBTREE_TOP(t->sentinel);
    ms_stree_node where = t->sentinel;
    while (node != t->sentinel) {
        if (t->fs.key_cmp(t->fs.key_fn(node->p), key)) {
            node = node->right;
        }
        else {
            where = node;
            node = node->left;
        }
    }
    return where;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}
//greater than key
CPUBLIC ms_stree_node ms_stree_upper_bound(ms_stree t, MS_TREEKEY key) {
#ifdef _IF_NULL_
    if (t) {
#endif
    ms_stree_node node = (ms_stree_node)MS_RBTREE_TOP(t->sentinel);
    ms_stree_node where = t->sentinel;
    while (node != t->sentinel) {
        if (t->fs.key_cmp(key, t->fs.key_fn(node->p))) {
            where = node;
            node = node->left;
        }
        else {
            node = node->right;
        }
    }
    return where;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

#endif // MSC_STREE_H
